1. Field of the Invention
The present invention relates generally to scheduling transmissions in communication systems.
2. Description of Related Art
New technical challenges emerge as telecommunication systems evolve from a second generation system offering pure voice services to a third generation system providing mixed voice and data services. In meeting data service demands, new performance metrics and algorithms need to be defined in order to optimize data performance.
The CDMA 3G-1x Evolution Data Only system (1x-EV-DO, also known as a High Rate Packet Data (HRPD) system) is an evolution system of cdma2000 3G-1x system, and is a pure data system to provide data services to mobile users. In 1x-EV-DO, a scheduler or scheduling function is provided in a base station controller in order to provide fast scheduling or management of system resources based on channel quality feedback from one or more mobiles. In general, a scheduler selects a mobile for transmission at a given time instant, and adaptive modulation and coding allows selection of the appropriate transport format (modulation and coding) for the current channel conditions seen by the mobile.
In second generation wireless communications systems such as those of the IS-95 standard, applications typically employ voice-based communication schemes, in which a connection between the base station and the mobile is a dedicated connection. Since these are essentially fixed connections, there is no need for prioritizing the order of transmission to the active users served by the system (an active user is a user with data to transmit at a current time instant). However, with the emergence of third generation wireless data communications systems, such as CDMA-2000 standard systems and 1x-EV-DO, management of system resources is paramount. This is because properties of data differ significantly from properties of voice. For example, a data transmission, unlike a voice transmission, is not necessarily continuous and may be embodied as a burst transmission or an intermittent-type transmission between a base station and a mobile, for example. Accordingly, a base station in a third-generation system will attempt to manage a large pool of data users by assigning radio resources to each user for transmission. Typically this is done utilizing a prioritization scheme controlled by a scheduler in the base station controller. In a conventional prioritization scheme, idle mobile's are assigned a lower priority than mobile with data to transmit.
Accordingly, the scheduler must be able to manage these large numbers of users without wasting radio resources of the communication system. This management function becomes even more important as a base station attempts to meet QoS (Quality of Service) requirements. QoS is a general term that may represent a number of different requirements. As a basic tenant, QoS is indicative of providing guaranteed performance (e.g., such as a minimum/maximum data network throughput, a minimum delay requirement, a packet loss rate, and a packet download time, etc.) in a wireless communication system.
Quality of Service (QoS) differentiation in wireless data networks allows network operators to generate more revenue than is possible with best-effort scheduling policies. The promise of additional revenue is based on the willingness of end users (subscribers) to pay more for perceptible improvements in service (e.g., lower latency, higher throughput, or more predictable performance). QoS differentiation also enables deployment of new services (e.g., streaming audio/video, packet voice etc.) that cannot be provided with acceptable quality over best-effort scheduling policies or algorithms such as highest rate user first (HRUF)) scheduling, maximum carrier to interference ratio scheduling (Max C/I) and proportional fair (PF) scheduling, etc.
There has been efforts to develop scheduling algorithms for the scheduler in the base station controller to achieve QoS guarantees in wired and wireless networks. Prior efforts have resulted in scheduling techniques such as pure peak picking scheduling (i.e., the aforementioned HRUF or Max C/I)) and proportional fair (PF) scheduling, for example. HRUF maximizes system throughput at the expense of being unfair to users in poor channel conditions. For example, in HRUF scheduling, a user at a significant distance from a serving base station, such as a user that may be located at the edge of a cell, for example, would have significantly lower priority, on average, than a user in close proximity to the base station within the cell. When the variation of the channel is small, this can potentially result in the user at the edge of cell getting almost no service. Similarly, Max C/I assigns priority to users based on the highest signal-to-noise ratio (SNR) of the user.
The PF algorithm attempts to exploit multi-user diversity while ensuring a certain degree of fairness. In Proportional Fair scheduling, the scheduler keeps track of two values, in particular, for each user: DRC and R. On the downlink of a wireless network, for example, each user will estimate its signal to noise ratio (SNR) for the next timeslot, and on that basis will select a rate for transmission of downlink data from the base station. The selection will typically be the highest available rate consistent with a specified frame error rate, or other such error rate. The transmission rate requested by a given user in a given timeslot is DRC.
The second value, R, is the rate at which a given mobile station (user) has received data from the base station, or other hub, as averaged by an appropriate procedure such as exponentially weighted averaging using a desired time constant. In each timeslot n, the Proportional Fair scheduler will serve that user for which the ratio DRC/R is greatest. Thus, each user tends to receive service in those timeslots where its requested rate is highest—not in an absolute sense, but, rather, highest relative to the average rate (average user throughput) at which that particular user has been receiving data in the recent past. Because that average user throughput rate will be small for underserved users, even a user with a poor channel will eventually be served. That is, the average rates are dynamic quantities, and they will converge toward a condition in which each user is served reasonably often.
Since none of the above algorithms explicitly attempt to satisfy minimum user throughput requirements, use of these algorithms may lead to a high degree of dissatisfaction among users. For example, certain minimum throughputs are required in order to provide certain services such as audio or video streaming; thus scheduling algorithms which do not meet these minimum throughput requirements may not be able to offer such services. Further, the above algorithms do not focus on ways of enforcing maximum user throughput to exploit peaks in channel quality being experienced by users in the network or system. In order to constrain the maximum throughput achieved by a user in a network, most scheduling algorithms, including the HRUF and PF algorithms described above, simply disallow a user from being scheduled once the user reaches a target maximum throughput constraint.